#include <dbg.h>

#include <cassert>

using namespace std;

class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0;
        int left_max = 0;  // 左右最高柱子
        int right_max = 0;

        int left = 0;  // 左右指针
        int right = height.size() - 1;
        while (left <= right) {
            // 更新左右最高柱子
            left_max = max(left_max, height[left]);
            right_max = max(right_max, height[right]);
            if (left_max < right_max) {  // 左边低，可以确定左边的柱子的储水量
                res += left_max - height[left];
                ++left;  // 移动左指针
            } else {     // 右边低，可以确定右边的柱子的储水量
                res += right_max - height[right];
                --right;  // 移动右指针
            }
        }
        return res;
    }
};

int main() {
    Solution s;

    vector<int> height1{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    vector<int> height2{4, 2, 0, 3, 2, 5};

    assert(s.trap(height1) == 6);
    assert(s.trap(height2) == 9);

    return 0;
}